// 给出一个完全二叉树，求出该树的节点个数。

// 说明：

// 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

// 示例:

// 输入: 
//     1
//    / \
//   2   3
//  / \  /
// 4  5 6

// 输出: 6

#include <cmath>
#include <queue>

using std::queue;
using std::pow;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 二分法
class Solution {
public:
    int countNodes(TreeNode* root) {
        TreeNode* cur = root;
        int level{1};
        int depth = getDepth(root);
        int nums{0};
        while(cur != nullptr) {
            TreeNode* temp = cur->right;
            if ((level + getDepth(temp) == depth) &&
                (temp != nullptr))
            {
                cur = cur->right;
                nums += pow(2, depth - level - 1);
                ++level;    
            } else {
                cur = cur->left;
                ++level;
            }
        }
        return nums + pow(2, depth-1);
    }
    // 得到树的深度（高度）
    int getDepth(TreeNode* root) {
        int depth{0};
        while(root) {
            ++depth;
            root = root->left;
        }
        return depth;
    }
};

// 非递归，层序遍历，使用队列
class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> q{};
        int res{0};
        if (root != nullptr) q.push(root);
        while(!q.empty()) {
            TreeNode* temp = q.front();
            q.pop();
            if (temp->left != nullptr) q.push(temp->left);
            if (temp->right != nullptr) q.push(temp->right);
            ++res;
        }
        return res;
    }
};

// 递归
class Solution1 {
public:
    int countNodes(TreeNode* root) {
        fun(root);
        return count_nodes;
    }
    void fun(TreeNode* node) {
        if (nullptr == node) return;
        ++count_nodes;
        if (nullptr != node->left) fun(node->left);
        if (nullptr != node->right) fun(node->right);
    }
private:
    int count_nodes{0};
};

class Solution2 {
public:
    int countNodes(TreeNode* root) {
        if (nullptr == root) return 0;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

class Solution3 {
public:
    int countNodes(TreeNode* root) {
        if (nullptr == root) return 0;
        int leftNodes = countNodes(root->left);
        int rightNodes = countNodes(root->right);
        return leftNodes + rightNodes + 1;
    }
};

#include "stdc++.h"

/* level order
*/
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        int res{0};
        queue<TreeNode*> q{};
        q.push(root);
        while (!q.empty()) {
            ++res;
            TreeNode* node = q.front();
            q.pop();
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
        return res;
    }
};

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int level{0};
        TreeNode* node{root};
        while (node->left != nullptr) {
            ++level;
            node = node->left;
        }
        int low = (1 << level);
        int high = (1 << (level + 1)) - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (exists(root, level, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
    bool exists(TreeNode* root, int level, int k) {
        int bits = (1 << (level - 1));
        TreeNode* node = root;
        while (node != nullptr && bits > 0) {
            if (0 == (bits & k)) {
                node = node->left;
            } else {
                node = node->right;
            }
            bits >>= 1;
        }
        return node != nullptr;
    }
};